package com.tree.leetcode.linklist;

import com.tree.leetcode.common.ListNode;

import java.util.HashSet;
import java.util.Set;

import static com.tree.leetcode.common.ListNode.nodeBuilder;
import static com.tree.leetcode.common.ListNode.printNodeResult;

/**
 * @ClassName com.tree.leetcode.linklist
 * Description: 160. 相交链表
 * https://leetcode.cn/problems/intersection-of-two-linked-lists/?envType=study-plan-v2&envId=top-100-liked
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，
它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
 * </p>
 * @Author tree
 * @Date 12/10/23 10:46 PM
 * @Version 1.0
 */
public class IntersectionNode_164 {

    public static void main(String[] args) {
        com.tree.leetcode.common.ListNode node1 = nodeBuilder(new int[]{4,1,8,4,5});
        com.tree.leetcode.common.ListNode node2 = nodeBuilder(new int[]{5,6,1,8,4,5});
        ListNode result = getIntersectionNode2(node1,node2);
        printNodeResult(result);

    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<>();
        ListNode temp = headA;
        while (temp != null) {
            visited.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null) {
            if (visited.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }


    public static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {return null;}
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }


//    public class ListNode {
//        int val;
//        ListNode next;
//
//        ListNode(int x) {
//            val = x;
//            next = null;
//        }
//    }

}
